# 给定一个二维矩阵 matrix，以下类型的多个请求：
#  计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
#
#  实现 NumMatrix 类：
#  NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
#  int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下
# 角 (row2, col2) 所描述的子矩阵的元素 总和 。
#
#  示例 1：
# 输入:
# ["NumMatrix","sumRegion","sumRegion","sumRegion"]
# [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],
# [2,1,4,3],[1,1,2,2],[1,2,2,4]]
# 输出:
# [null, 8, 11, 12]
#
# 解释:
# NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
# numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
# numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
# numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
from typing import List


class NumMatrix:
    """
    解法二：二维前缀和
    preSums[i][j] 表示 以 matrix[0][0]为左上角，matrix[i][j]为右下角的矩阵的和
    """
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.preSums = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.preSums[i][j] = self.preSums[i - 1][j] + self.preSums[i][j - 1] - self.preSums[i - 1][j - 1] + matrix[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSums[row2 + 1][col2 + 1] - self.preSums[row2 + 1][col1] - self.preSums[row1][col2 + 1] + self.preSums[row1][col1]


class NumMatrix1:
    """
    解法一: 一维前缀和
    preSums[i] 为 matrix[i] 的前缀和数组
     即 preSums[i][j] = matrix[i][0] + matrix[i][1] + matrix[i][2] + ... + matrix[i][j]
    所以有sumRegion(row1, col1, row2, col2) = sum(preSums[i][col2 + 1] - preSums[i][col1]) 其中 row1 <= i <= row2
    """
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.preSums = [[0] * (n + 1) for _ in range(m)]
        for i in range(m):
            for j in range(1, n + 1):
                self.preSums[i][j] = self.preSums[i][j - 1] + matrix[i][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for i in range(row1, row2 + 1):
            res += self.preSums[i][col2 + 1] - self.preSums[i][col1]
        return res


if __name__ == '__main__':
    matrix = [
        [3, 0, 1, 4, 2],
        [5, 6, 3, 2, 1],
        [1, 2, 0, 1, 5],
        [4, 1, 0, 1, 7],
        [1, 0, 3, 0, 5]]
    numMatrix = NumMatrix(matrix)
    print(numMatrix.sumRegion(2, 1, 4, 3))  # return 8
    print(numMatrix.sumRegion(1, 1, 2, 2))  # return 11
    print(numMatrix.sumRegion(1, 2, 2, 4))  # return 12

    numMatrix = NumMatrix1(matrix)
    print(numMatrix.sumRegion(2, 1, 4, 3))  # return 8
    print(numMatrix.sumRegion(1, 1, 2, 2))  # return 11
    print(numMatrix.sumRegion(1, 2, 2, 4))  # return 12
